package com.springboot.demo.tree;

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;

/**
 * 二叉树
 *
 * @author supu
 * @date 2019-07-22 15:34
 **/
public class BinaryTree<T extends Comparable<T>> {
    //根节点
    private Node root;

    class Node {
        //节点数据
        private T data;
        //父节点
        private Node parent;
        //左子节点
        private Node leftChild;
        //右子节点
        private Node rightChild;

        // 构造方法
        public Node(T data) {
            this.data = data;
        }
    }

    public Node root() {
        return root;
    }

    /**
     * 前序遍历（即深度遍历）（中->左->右）
     *
     * @param node
     */
    public void preOrder(Node node) {
        if (node != null) {
            System.out.print(node.data + ",");
            preOrder(node.leftChild);
            preOrder(node.rightChild);
        }
    }

    /**
     * 中序遍历（即深度遍历）（左->中->右）
     *
     * @param node
     */
    public void middleOrder(Node node) {
        if (node != null) {
            middleOrder(node.leftChild);
            System.out.print(node.data + ",");
            middleOrder(node.rightChild);
        }
    }

    /**
     * 后序遍历（即深度遍历）（左->右->中）
     *
     * @param node
     */
    public void afterOrder(Node node) {
        if (node != null) {
            afterOrder(node.leftChild);
            afterOrder(node.rightChild);
            System.out.print(node.data + ",");
        }
    }

    /**
     * 增加节点
     *
     * @param data
     * @return
     */
    public boolean add(T data) {
        boolean flag = false;
        if (!exist(data)) {
            Node newNode = new Node(data);
            if (root == null) {
                root = newNode;
            } else {
                // 找到父节点
                Node parent = findParent(data);
                if (parent != null) {
                    if (parent.data.compareTo(data) > 0) {
                        parent.leftChild = newNode;
                    } else {
                        parent.rightChild = newNode;
                    }
                    //新建节点的parent指向父节点
                    newNode.parent = parent;
                }
            }
            flag = true;
        }
        return flag;
    }

    /**
     * 删除节点
     *
     * @param data
     * @return
     */
    public boolean remove(T data) {
        boolean flag = false;
        Node node = getNode(data);
        if (node != null) {
            if (node == root) {
                // 删除的是根节点
                if (node.leftChild == null && node.rightChild == null) {
                    root = null;
                } else if (node.leftChild != null && node.rightChild == null) {
                    node.leftChild.parent = null;
                    root = node.leftChild;
                } else if (node.leftChild == null && node.rightChild != null) {
                    node.rightChild.parent = null;
                    root = node.rightChild;
                } else {
                    //找到要删节点的左节点
                    Node leftChild = split(data);
                    root = leftChild;
                    leftChild.parent = null;
                }
            } else {
                // 删除的是根节点
                if (node.leftChild == null && node.rightChild == null) {
                    if (node.data.compareTo(node.parent.data) < 0) {
                        node.parent.leftChild = null;
                    } else {
                        node.parent.rightChild = null;
                    }
                } else if (node.leftChild != null && node.rightChild == null) {
                    node.leftChild.parent = node.parent;
                    node.parent.rightChild = node.leftChild;
                } else if (node.leftChild == null && node.rightChild != null) {
                    node.rightChild.parent = node.parent;
                    node.parent.rightChild = node.rightChild;
                } else {
                    //找到要删节点的左节点
                    Node leftChild = split(data);
                    node.parent.leftChild = node.leftChild;
                    leftChild.parent = node.parent;
                }
            }
            flag = true;
        }
        return flag;
    }

    /**
     * 节点是否存在
     *
     * @param data
     * @return
     */
    public boolean exist(T data) {
        boolean flag = false;
        //从根节点开始遍历
        Node temp = root;
        while (temp != null) {
            if (temp.data.compareTo(data) == 0) {
                flag = true;
            } else if (temp.data.compareTo(data) > 0) {
                temp = temp.leftChild;
            } else {
                temp = temp.rightChild;
            }
        }
        return flag;
    }

    /**
     * 获取节点
     *
     * @param data
     * @return
     */
    public Node getNode(T data) {
        //从根节点开始遍历
        Node temp = root;
        while (temp != null) {
            if (temp.data.compareTo(data) == 0) {
                return temp;
            } else if (temp.data.compareTo(data) > 0) {
                temp = temp.leftChild;
            } else {
                temp = temp.rightChild;
            }
        }
        return null;
    }

    /**
     * 查找节点的父节点
     *
     * @param data
     * @return
     */
    public Node findParent(T data) {
        //从根节点开始遍历
        Node temp = root;
        Node prev = temp;
        while (temp != null) {
            //跳出循环时，temp 为 null，prev记录上一个节点，即为parent
            prev = temp;
            if (temp.data.compareTo(data) > 0) {
                temp = temp.leftChild;
            } else {
                temp = temp.rightChild;
            }
        }
        return prev;
    }

    /**
     * 左右分隔节点
     *
     * @param data
     * @return
     */
    public Node split(T data) {
        //找到节点
        Node node = getNode(data);
        //找到左节点的最大数节点
        Node big = getBig(node.leftChild);
        //将要分割节点的右节点的parent指向big
        node.rightChild.parent = big;
        //将big的右节点指向node的右节点
        big.rightChild = node.rightChild;
        return node.leftChild;
    }

    /**
     * 获取最大节点
     *
     * @param node
     * @return
     */
    public Node getBig(Node node) {
        Node temp = node;
        while (temp != null) {
            if (temp.rightChild != null) {
                temp = temp.rightChild;
            } else {
                return temp;
            }
        }
        return null;
    }

    /**
     * 创建二叉树
     *
     * @param list
     * @return
     */
    public static BinaryTree createBinaryTree(List<Integer> list) {
        BinaryTree<Integer> binaryTree = new BinaryTree();
        for (Integer integer : list) {
            binaryTree.add(integer);
        }
        return binaryTree;
    }

    /**
     * 递归获取二叉树深度
     *
     * @return
     */
    public int recursiveGetTreeHeight(Node root) {
        if (root == null) {
            return 0;
        }
        int leftHeight = recursiveGetTreeHeight(root.leftChild);
        int rightHeight = recursiveGetTreeHeight(root.rightChild);
        return leftHeight >= rightHeight ? leftHeight + 1 : rightHeight + 1;
    }

    /**
     * 非递归获取二叉树深度(广度遍历)
     * <p>
     * 思想：从根节点开始逐层遍历，每遍历完一层，层数+1
     *
     * @return
     */
    public int normalGetTreeHeight(Node root) {
        if (root == null) {
            return 0;
        }
        // levelCount 每层节点总数，cursorIndex 当前层访问到的节点个数
        int levelCount, cursorIndex;
        Queue<Node> queue = new LinkedList<>();
        // 先将根节点放入链表list中
        queue.offer(root);
        // 二叉树高度
        int hight = 0;
        // 遍历的当前节点
        Node currentNode;
        while (!queue.isEmpty()) {
            cursorIndex = 0;
            levelCount = queue.size();
            while (cursorIndex < levelCount) {
                cursorIndex++;
                currentNode = queue.poll();
                if (currentNode.leftChild != null) {
                    queue.offer(currentNode.leftChild);
                }
                if (currentNode.rightChild != null) {
                    queue.offer(currentNode.rightChild);
                }
            }
            // 遍历完一层，层数+1
            hight++;
        }
        return hight;
    }

    /**
     * 非递归深度优先遍历，采用栈实现（先进后出）
     * <p>
     * 思想：沿着某一个分支一直遍历到底，利用此特点可以使用栈，先将右节点入栈、然后再左节点入栈，这样子出栈就是先左节点然后右节点
     *
     * @param root
     */
    public void depthFirstSearch(Node root) {
        if (root == null) {
            return;
        }
        Stack<Node> stack = new Stack<>();
        stack.push(root);
        Node currentNode;
        while (!stack.empty()) {
            currentNode = stack.pop();
            System.out.print(currentNode.data + ",");
            if (currentNode.rightChild != null) {
                stack.push(currentNode.rightChild);
            }
            if (currentNode.leftChild != null) {
                stack.push(currentNode.leftChild);
            }
        }
    }

    /**
     * 递归深度优先遍历，采用栈实现（先进后出）
     * <p>
     * 思想：沿着某一个分支一直遍历到底，利用此特点可以使用栈，先将右节点入栈、然后再左节点入栈，这样子出栈就是先左节点然后右节点
     *
     * @param root
     */
    public void recursionDepthFirstSearch(Node root) {
        if (root == null) {
            return;
        }
        System.out.print(root.data + ",");
        recursionDepthFirstSearch(root.leftChild);
        recursionDepthFirstSearch(root.rightChild);
    }


    /**
     * 广度优先遍历，采用队列实现（先进先出）
     * <p>
     * 思想：从左到右一层层的遍历,先往队列中插入左节点，再插右节点，这样出队就是先左后右了
     *
     * @param root
     */
    public void breadthFirstSearch(Node root) {
        if (root == null) {
            return;
        }

        Queue<Node> queue = new LinkedList<>();
        queue.offer(root);
        Node currentNode;
        while (!queue.isEmpty()) {
            currentNode = queue.poll();
            System.out.print(currentNode.data + ",");
            if (currentNode.leftChild != null) {
                queue.offer(currentNode.leftChild);
            }
            if (currentNode.rightChild != null) {
                queue.offer(currentNode.rightChild);
            }
        }
    }
}
